package com.Oct_Sixteen;

/**
 * 886. 可能的二分法
 * 给定一组 n 人（编号为 1, 2, ..., n）， 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。
 *
 * 给定整数 n 和数组 dislikes ，其中 dislikes[i] = [ai, bi] ，表示不允许将编号为 ai 和  bi的人归入同一组。当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/possible-bipartition
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/10/16 23:00
 */

public class Solution886 {

    public boolean possibleBipartition(int n, int[][] dislikes) {
        int[][] graph=new int[n][n];
        for (int[] d:dislikes){
            graph[d[0]-1][d[1]-1]=1;
            graph[d[1]-1][d[0]-1]=1;
        }
        int[] group=new int[n];
        for (int i=0;i<n;i++)
        {
            //无法分组的
            if (group[i]==0&&!dfs(graph,group,i,1))
            {
                return false;
            }
        }
        return true;
    }

    boolean dfs(int[][] graph,int[] group,int index,int g){
        group[index]=g;
        for (int i=0;i<graph.length;i++)
        {
            if (graph[index][i]==1)
            {
                //不喜欢的人属于同一阵营
                if (group[i]==g)
                {
                    return false;
                }
                //不喜欢的人可以分到同一组
                if (group[i]==0&&!dfs(graph,group,i,-g))
                {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution886 solution886=new Solution886();
        System.out.println(solution886.possibleBipartition(4,new int[][]{{1,2},{1,3},{2,4}}));
    }

}
